%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Sage for High School
%% http://code.google.com/p/high-school-sage/
%%
%% Copyright (C) 2010 Minh Van Nguyen <nguyenminh2@gmail.com>
%%
%% See the file COPYING for copying conditions. See the file LICENSE
%% for the terms under which the whole book is licensed.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Number Theory}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Integers}
\index{integer}

An \emph{integer}\index{integer} is a whole number. It can be
positive, negative, or zero. Examples of integers include $-13$, $-1$,
$0$, and $42$. When we talk about all the whole numbers, we can use
the name \emph{integer}\index{integer} to refer to them, or we can
list all the whole numbers like so:
\[
\dots, -4, -3, -2, -1, 0, 1, 2, 3, 4, \dots
\]
But for convenience, we usually write $\ZZ$\index{$\ZZ$} to denote the
set of all integers:
\[
\ZZ
=
\{\dots, -3, -2, -1, 0, 1, 2, 3, \dots\}.
\]
In Sage, the set of all integers is represented as \verb!ZZ! and a
single integer is represented using \verb!Integer!:
%
\begin{lstlisting}
sage: ZZ
Integer Ring
sage: type(ZZ)
<type 'sage.rings.integer_ring.IntegerRing_class'>
sage: 1 in ZZ
True
sage: -1 in ZZ
True
sage: 3.1415 in ZZ
False
sage: type(3)
<type 'sage.rings.integer.Integer'>
sage: Integer
<type 'sage.rings.integer.Integer'>
\end{lstlisting}
%
Notice that in the above code listing, we used \verb!in! to test
whether or not a number is an integer. The command
%
\begin{lstlisting}
sage: 1 in ZZ
True
\end{lstlisting}
%
gives the result \verb!True! because $1$ is an integer. On the other
hand, the command
%
\begin{lstlisting}
sage: 3.1415 in ZZ
False
\end{lstlisting}
%
gives \verb!False! because $3.1415$ is not an integer.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Prime numbers}
\index{prime}

A positive integer $n > 1$ is a \emph{prime}\index{prime} number if
its factors are exclusively $1$ and itself. The integer $2$ is prime
because its only factors are $1$ and $2$. As a matter of fact, $2$ is
the smallest prime integer. The next prime after $2$ is $3$. However,
the next integer $4$ is not prime because $2$ is a factor of $4$. In
Sage, the command \verb!is_prime! tests whether or not an integer is
prime. We can obtain the first $15$ prime numbers using the command
\verb!primes_first_n!.

\begin{lstlisting}
sage: is_prime(1)
False
sage: is_prime(2)
True
sage: is_prime(3)
True
sage: is_prime(4)
False
sage: primes_first_n(15)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
\end{lstlisting}

If $n$ is an integer, the command \verb!next_prime! can be used to
compute the next prime integer starting from $n$. Likewise, the command
\verb!previous_prime! computes the previous prime integer starting
from $n$.
%
\begin{lstlisting}
sage: next_prime(-25)
2
sage: next_prime(1)
2
sage: next_prime(50)
53
sage: previous_prime(50)
47
sage: previous_prime(3)
2
sage: previous_prime(2)
Traceback (most recent call last):
...
ValueError: no previous prime
\end{lstlisting}
%
The command
%
\begin{lstlisting}
sage: next_prime(-25)
2
\end{lstlisting}
%
results in \verb!2! because $2$ is the smallest prime. In other words,
there are no primes smaller than $2$, which explains the result of the
following command:
%
\begin{lstlisting}
sage: previous_prime(2)
Traceback (most recent call last):
...
ValueError: no previous prime
\end{lstlisting}

There are various questions we can ask about prime\index{prime}
numbers. For example, how many prime integers are there? Over two
thousand years ago, the Greek mathematician Euclid\index{Euclid}
proved that there are infinitely many primes. No matter how high up we
count, there is still a prime number to be found.

Here's another question: If $n$ is a positive integer greater than
$1$, how many primes are there between $1$ and $n$? In the case of
$n = 50$, we could use the command \verb!primes_first_n! to list the
first 20 primes, then count how many of those primes are less than or
equal to $50$.
%
\begin{lstlisting}
sage: primes_first_n(20)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
sage: P = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]; P
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
sage: len(P)
15
\end{lstlisting}
%
In the above code listing, we put all the primes less than or equal to
$50$ into the list \verb!P!. We then used the command \verb!len! to
obtain the length of that list. From the above output, there are $15$
primes less than or equal to $n = 50$.

Alternatively, we can let the command \verb!prime_pi!\index{$\pi(x)$}
do all the hard work for us. Given an integer $n$---either positive,
negative, or zero---the command \verb!prime_pi(n)! counts how many
primes are less than or equal to $n$.
%
\begin{lstlisting}
sage: prime_pi(50)
15
sage: prime_pi(100)
25
sage: prime_pi(1000)
168
sage: prime_pi(10000)
1229
sage: prime_pi(0)
0
sage: prime_pi(-10)
0
\end{lstlisting}
%
To study the output of \verb!prime_pi(n)!\index{$\pi(x)$} as the
integer \verb!n! increases, we could substitute $n = 1, 2, 3, \dots$
into the command. Or we could use \verb!plot! together with
\verb!prime_pi! to visualize how the output of \verb!prime_pi! changes
as $n$ increases in
value. Figure~\ref{fig:number_theory:prime_pi_for_n_leq_100}
illustrates the change in the values of \verb!prime_pi! as $n$ takes
on all integer values from $0$ up to and including $100$. Notice that
when $n = 50$, the output of \verb!prime_pi! is $15$, which confirms
our computation above. The horizontal axis shows integer values of $n$
from $0$ to $100$, inclusive, while the vertical axis shows the output
of the command \verb!prime_pi(n)!. The figure was produced using the
following code listing:
%
\begin{lstlisting}
sage: P = plot(prime_pi, 0, 100)
sage: V = line([(50,0), (50,25)], color="red")     # vertical line
sage: H = plot(15, xmin=0, xmax=100, color="red")  # horizontal line
sage: P + H + V
\end{lstlisting}
%
\begin{figure}[!htbp]
\centering
\includegraphics[scale=0.8]{images/prime-pi-100}
\caption{Values of \texttt{prime\_pi(n)} for $n = 0, 1, 2, \dots, 100$.}
\label{fig:number_theory:prime_pi_for_n_leq_100}
\end{figure}
%
And Figure~\ref{fig:number_theory:prime_pi_for_n_leq_1000} shows the
behavior of \verb!prime_pi! as $n$ increases from $0$ to $1000$. The
figure was produced using the command:
%
\begin{lstlisting}
sage: plot(prime_pi, 0, 1000)
\end{lstlisting}
%
\begin{figure}[!htbp]
\centering
\includegraphics[scale=0.8]{images/prime-pi-1000}
\caption{Values of \texttt{prime\_pi(n)} for $n = 0, 1, 2, \dots, 1000$.}
\label{fig:number_theory:prime_pi_for_n_leq_1000}
\end{figure}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Divisibility}
\index{divisibility}

For any two integers $a$ and $n$, we say that $a$
\emph{divides}\index{divides} $n$ if $a$ is a factor of $n$. That is,
if we can find an integer $b$ such that $n = ab$, then $a$ is a
factor\index{factor} of $n$. In that case, $b$ is also a factor of
$n$. The integer $2$ divides, or is a factor of, $4$ because
$4 = 2 \times 2$. Similarly, both $2$ and $3$ are factors of, or both
divide, $6$ because $6 = 2 \times 3$.

Does every positive integer have a factor\index{factor}? Yes. In fact,
if $n > 1$ is an integer, then $n$ has a factor that is greater than
$1$. We can make a stronger claim: Every integer $n > 1$ has a prime
factor. A factorization, or prime factorization, of $n$ is product
containing all the primes that divide $n$. Examples of prime
factorizations include $4 = 2 \times 2$ and $6 = 2 \times 3$. However,
$8 = 2 \times 4$ is not a prime factorization of $8$ because the
product $2 \times 4$ has $4$, which is not prime.

To find all the positive divisors\index{divisor} of an integer, use
the command \verb!divisors!.
%
\begin{lstlisting}
sage: divisors(4)
[1, 2, 4]
sage: divisors(6)
[1, 2, 3, 6]
sage: divisors(8)
[1, 2, 4, 8]
\end{lstlisting}
%
To write $n$ as a product of primes, use \verb!factor!.

\begin{lstlisting}
sage: factor(4)
2^2
sage: factor(6)
2 * 3
sage: factor(8)
2^3
\end{lstlisting}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Greatest common divisors}
\index{greatest common divisor}

Let $a$ and $b$ be integers, not both zero. The
\emph{greatest common divisor}\index{greatest common divisor}
(GCD)\index{GCD} of $a$ and $b$ is the largest positive integer which
is a factor of both $a$ and $b$. We use $\gcd(a,b)$ to denote this
largest positive factor. If $n$ is any positive integer, then
$\gcd(n, 0) = n = \gcd(0, n)$. If $a$ and $b$ are both zero, then we
define their GCD to be $\gcd(0,0) = 0$. The GCD\index{GCD} of any two
distinct primes is $1$, and the GCD of $18$ and $27$ is $9$.
%
\begin{lstlisting}
sage: gcd(0, 0)
0
sage: gcd(12, 0)
12
sage: gcd(13, 0)
13
sage: N = [1..20]; N
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
sage: G = []
sage: for i in N:
...       G.append(gcd(i, 0))
sage: N
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
sage: G
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
\end{lstlisting}
%
In the above code listing, we used the command \verb![1..20]! to
obtain a list of all integers from $1$ to $20$, inclusive.

To find the GCD of $18$ and $27$, we could first use \verb!divisors!
to find the set of all positive divisors of each integer. We then
compare the set of divisors for $18$ with that for $27$, picking out
any integers that are common to both sets. From among all the divisors
that are common to both $18$ and $27$, we choose the largest such
divisor. The result is the GCD of $18$ and $27$.
%
\begin{lstlisting}
sage: D18 = Set(divisors(18)); D18
{1, 2, 3, 6, 9, 18}
sage: D27 = Set(divisors(27)); D27
{3, 1, 27, 9}
sage: D = D18.intersection(D27); D
{1, 3, 9}
sage: max(D)
9
\end{lstlisting}
%
The output of \verb!divisors! is a list. We used the command
\verb!Set!\index{set} to convert the result of \verb!divisors! into a
set. We then used \verb!intersection!\index{intersection} to produce
the intersection of the two sets \verb!D18! and \verb!D27!; this
intersection is the set \verb!D!. Finally, we used \verb!max! to
compute the maximum element in the set \verb!D!, i.e. $9$, the GCD we
require.

Sage uses \verb!gcd(a, b)! to denote the GCD of $a$ and $b$. The GCD
of any two integers can be computed as follows:
%
\begin{lstlisting}
sage: gcd(3, 59)
1
sage: gcd(18, 27)
9
\end{lstlisting}

What about the case where any of $a$ and $b$ is negative? For example,
how do we compute the GCD of $-18$ and $27$, or $\gcd(-18, -27)$? If
$a$ is negative, for example, then we compute its
\emph{absolute value}\index{absolute value} and use that value to find
the GCD of $a$ and $b$. The absolute value of a number $x$ is written
as $|x|$ and is defined as
\[
|x|
=
\begin{cases}
x, & \text{if $x \geq 0$}, \\
-1 \times x, & \text{if $x < 0$}.
\end{cases}
\]
For example, the absolute value of $27$ is $|27| = 27$ because
$27 \geq 0$; the absolute value of $-18$ is
$|-18| = -1 \times (-18) = 18$ because $-18$ is negative. Then the GCD
of $-18$ and $27$ is
%
\begin{align*}
\gcd(-18, 27)
&=
\gcd(|-18|, 27) \\
&=
\gcd(18, 27) \\
&=
9.
\end{align*}

\begin{lstlisting}
sage: gcd(18, 27)
9
sage: gcd(-18, 27)
9
sage: gcd(-18, -27)
9
sage: # positive values of a, with b = 27
sage: N = [1..10]; N
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
sage: G = []
sage: for i in N:
...       G.append(gcd(i, 27))
sage: G
[1, 1, 3, 1, 1, 3, 1, 1, 9, 1]
sage: # negative values of a, with b = 27
sage: N = [-1..-10, step=-1]; N
[-1, -2, -3, -4, -5, -6, -7, -8, -9, -10]
sage: G = []
sage: for i in N:
...       G.append(gcd(i, 27))
sage: G
[1, 1, 3, 1, 1, 3, 1, 1, 9, 1]
\end{lstlisting}

Figure~\ref{fig:number_theory:gcd_n_27} plots $\gcd(n, 27)$ for
integer values of $n$ from $1$ to $100$, inclusive. The horizontal
axis shows the values of $n$, while the vertical axis shows the values
of $\gcd(n, 27)$.

\begin{figure}[!htbp]
\centering
\includegraphics[scale=1.0]{images/gcd-100}
\caption{The GCD of $n$ and $27$ for $n = 1, 2, \dots, 100$.}
\label{fig:number_theory:gcd_n_27}
\end{figure}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Relatively prime integers}
\index{relatively prime}
\index{coprime}

If $\gcd(a,b) = 1$, we say that $a$ is
\emph{coprime}\index{coprime}~(or relatively
prime\index{relatively prime}) to $b$.  In particular,
$\gcd(3, 59) = 1$ so $3$ is coprime to $59$ and vice versa.

Consider all the integers from $1$ to $20$, inclusive.  List all those
integers that are coprime to $20$.  In other words, find those
integers $n$, where $1 \leq n \leq 20$, such that
$\gcd(n,20) = 1$. The latter task can be easily accomplished with a
little bit of Sage programming:

\begin{lstlisting}
sage: for n in range(1, 21):
...       if gcd(n, 20) == 1:
...           print(n),
1 3 7 9 11 13 17 19
\end{lstlisting}

The above commands can be placed inside a function called
\verb!my_phi20! to save the hassle of retyping them every time we want
to use those exact commands.\index{Euler phi function}

\begin{lstlisting}
sage: def my_phi20():
...       for n in range(1, 21):
...           if gcd(n, 20) == 1:
...               print(n),
sage: my_phi20()
1 3 7 9 11 13 17 19
\end{lstlisting}
%
From the output of \verb!my_phi20!, note that there are $8$ integers
between $1$ and $20$, inclusive, that are coprime to $20$. Without
explicitly generating the list
%
\begin{equation}
\label{eq:integers_coprime_to_20}
1 \quad 3 \quad 7 \quad 9 \quad 11 \quad 13 \quad 17 \quad 19
\end{equation}
%
how can we compute the number of integers between $1$ and $20$,
inclusive, that are coprime to $20$? We could modify our function
\verb!my_phi20! so that it finds the number of positive integers that
are coprime to a given integer $n$.

\begin{lstlisting}
sage: def my_phi(n):
...       coprime = []
...       for i in range(1, n+1):
...           if gcd(i, n) == 1:
...               coprime.append(i)
...       return len(coprime)
sage: my_phi(20)
8
sage: my_phi(50)
20
sage: my_phi(100)
40
\end{lstlisting}

Alternatively, we could use the
\emph{Euler phi function}\index{Euler phi function}
$\varphi(n)$\index{$\varphi(n)$}, whose corresponding Sage built-in
function is \verb!euler_phi!.

\begin{lstlisting}
sage: euler_phi(20)
8
sage: euler_phi(50)
20
sage: euler_phi(100)
40
\end{lstlisting}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Least common multiples}
\index{least common multiple}
\index{LCM}

Let $a$ and $b$ be integers, both of which are not zero. The
\emph{least common multiple}\index{least common multiple}
(LCM\index{LCM}) of $a$ and $b$ is the smallest positive integer which
is a multiple of both $a$ and $b$. We write the least common multiple
of $a$ and $b$ as $\lcm(a, b)$. If $n$ is any integer, then $\lcm(n,
0) = 0$ and $\lcm(0, n) = 0$. Where $a$ and $b$ are both zero, then
$\lcm(0,0) = 0$.

\begin{lstlisting}
sage: lcm(0, 0)
0
sage: lcm(13, 0)
0
sage: lcm(42, 0)
0
sage: N = [1..20]; N
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
sage: L = []
sage: for i in N:
...       L.append(lcm(i, 0))
sage: N
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
sage: L
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
\end{lstlisting}

To compute the LCM of two integers $a$ and $b$, both of which are not
zero, first compute the GCD of $a$ and $b$. Finally, divide $ab$ by
$\gcd(a,b)$. This procedure is summarized in the following formula:
%
\begin{equation}
\label{eq:number_theory:formula_for_LCM}
\lcm(a, b)
=
\frac{ab}{\gcd(a, b)}.
\end{equation}
%
Using formula~(\ref{eq:number_theory:formula_for_LCM}), we have:
%
\begin{lstlisting}
sage: lcm(18, 27)
54
sage: (18 * 27) / gcd(18, 27)
54
sage: lcm(18, 0)
0
sage: (18 * 0) / gcd(18, 0)
0
sage: lcm(17, 19)
323
sage: (17 * 19) / gcd(17, 19)
323
sage: 17 * 19
323
\end{lstlisting}

Notice the special case of $17$ and $19$. These two integers are
primes, so their GCD is $\gcd(17, 19) = 1$.
Using~(\ref{eq:number_theory:formula_for_LCM}), we get
$\lcm(17, 19) = 17 \times 19$. In general, if $a$ and $b$ are both
prime integers, then $\gcd(a, b) = 1$ so that
formula~(\ref{eq:number_theory:formula_for_LCM}) simplifies to
\[
\lcm(a, b)
=
ab,
\qquad
\text{with $a,b$ being primes}.
\]


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Simplifying fractions}
\index{fraction}

A fraction such as $\frac{12}{8}$ can be simplified as follows. Find
the GCD of $12$ and $8$, and divide both the numerator and denominator
by $\gcd(12, 8)$. The GCD of $12$ and $8$ is $\gcd(12, 8) = 4$, so
%
\begin{align*}
\frac{12}{8}
&=
\frac{12 \div \gcd(12, 8)} {8 \div \gcd(12, 8)} \\[4pt]
&=
\frac{12 \div 4} {8 \div 4} \\[4pt]
&=
\frac{3}{2}.
\end{align*}
%
In general, let $a$ and $b$ be integers such that $b \neq 0$. If
$a = 0$, then $\frac{a}{b} = 0$. If $a \neq 0$, then the fraction
$\frac{a}{b}$ can be simplified as follows:
\[
\frac{a}{b}
=
\frac{a \div \gcd(a, b)} {b \div \gcd(a, b)}.
\]

\begin{lstlisting}
sage: # simplifying 12 / 8
sage: 12 / gcd(12, 8)
3
sage: 8 / gcd(12, 8)
2
sage: 12 / 8
3/2
sage: # simplifying 123 / 18
sage: 123 / gcd(123, 18)
41
sage: 18 / gcd(123, 18)
6
sage: 123 / 18
41/6
\end{lstlisting}

To add or subtract two fractions, we need to first express the
fractions with a common denominator. Then we can proceed to add or
subtract the resulting fractions. But first, how do we write both
fractions with a common denominator? We compute the LCM of both
denominators. Then multiply each fraction by that LCM divided by the
corresponding denominator. The procedure is summarized as follows. Let
$a,b,c,d$ be integers such that both $b$ and $d$ are not zero. Then
$\frac{a}{b}$ and $\frac{c}{d}$ can be added as follows:
%
\begin{equation}
\label{eq:number_theory:adding_fractions}
\begin{aligned}
\frac{a}{b} + \frac{c}{d}
&=
\left( \frac{\lcm(a,b)}{b} \times \frac{a}{\lcm(a,b)} \right)
+
\left( \frac{\lcm(a,b)}{d} \times \frac{c}{\lcm(a,b)} \right) \\[4pt]
&=
\frac{(\lcm(a,b) / b) \times a} {\lcm(a,b)}
+
\frac{(\lcm(a,b) / d) \times c} {\lcm(a,b)}.
\end{aligned}
\end{equation}

Using~(\ref{eq:number_theory:adding_fractions}), we add the fractions
$\frac{7}{5}$ and $\frac{6}{3}$ as follows:

\begin{lstlisting}
sage: L = lcm(5, 3)
sage: ((L/5) * 7) + ((L/3) * 6)
51
sage: L
15
sage: 51 / gcd(51, 15)  # numerator
17
sage: 15 / gcd(51, 15)  # denominator
5
sage: 51 / 15
17/5
sage: (7/5) + (6/3)
17/5
\end{lstlisting}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Clock arithmetic}
\index{clock arithmetic}
\index{congruence}

When one integer is divided by a nonzero integer, we usually get a
remainder. For example, upon dividing $23$ by $5$, we get a remainder
of $3$; when $8$ is divided by $5$, the remainder is again $3$. Clock
arithmetic, or congruence, is very useful for discussing the situation
in which two integers have the same remainder upon division by a
nonzero integer. Let $a,b,n$ be integers such that $n \neq 0$. If $a$
and $b$ have the same remainder upon division by $n$, then we say that
$a$ is \emph{congruent}\index{congruence} to $b$ modulo $n$ and denote
this relationship by writing
\[
a \equiv b \pmod{n}.
\]
This definition is equivalent to saying that $a - b$ is a factor of
$n$. Thus $23 \equiv 8 \pmod{5}$ because when both 23 and 8 are
divided by 5, we end up with a remainder of 3.

What has all this got to do with a clock, other than the name
``clock arithmetic''? To understand congruence, consider the standard
$12$-hour clock face\index{clock face} shown in
Figure~\ref{fig:number_theory:12_hour_clock_face}. The time $1$ AM
corresponds to $1$, $2$ AM corresponds to $2$, and so on, up to $12$
noon which corresponds to $12$. When we count past $12$ noon, it's
$1$~PM which corresponds to $13$. But how did we get from $13$ back to
$1$? We find the remainder when $13$ is divided by $12$; the required
remainder is $1$. Furthermore, $2$ PM corresponds to $14$. The number
$2$ is the remainder upon dividing $14$ by $12$. So when we count past
$12$, we start all over again from $1$. In this way, the integers from
$1$ up to and including $12$ form the twelve hours of a clock face. In
the notation of congruence, we write $1 \equiv 13 \pmod{12}$ and
$2 \equiv 14 \pmod{12}$.

\begin{figure}[!htbp]
\centering
\begin{tikzpicture}
[nodedecorate/.style={shape=circle,inner sep=2pt,draw,thick,fill=black},%
  linedecorate/.style={-,thick},%
  scale=3]
\draw [thick] (0,0) circle (1cm);
%% nodes or vertices
\foreach \nodename/\x/\y/\direction/\navigate in {
  1/0.5/0.866/above right/east, 2/0.866/0.5/right/east,
  3/1/0/right/east, 4/0.866/-0.5/right/east,
  5/0.5/-0.866/below right/east, 6/0/-1/below/south,
  7/-0.5/-0.866/below left/south, 8/-0.866/-0.5/left/west,
  9/-1/0/left/west, 10/-0.866/0.5/left/west,
  11/-0.5/0.866/above left/west, 12/0/1/above/north}
{
  \node (\nodename) at (\x,\y) [nodedecorate] {};
  \node [\direction] at (\nodename.\navigate) {$\nodename$};
}
\end{tikzpicture}
\caption{A $12$-hour clock face\index{clock face}.}
\label{fig:number_theory:12_hour_clock_face}
\end{figure}

The command \verb!mod!\index{$\bmod$} allows us to compute such a
remainder.

\begin{lstlisting}
sage: mod(23, 5)
3
sage: mod(8, 5)
3
sage: mod(1, 12)
1
sage: mod(2, 12)
2
sage: mod(13, 12)
1
sage: mod(14, 12)
2
\end{lstlisting}

If \verb!n! is an integer, we could also use \verb!n.quo_rem(m)! to
obtain the quotient\index{quotient} and remainder\index{remainder}
upon dividing \verb!n! by \verb!m!. The output of \verb!n.quo_rem(m)!
is a tuple consisting of two integers. The first integer is the
quotient and the second is the remainder.
%
\begin{lstlisting}
sage: 1.quo_rem(12)
(0, 1)
sage: q, r = 14.quo_rem(12)
sage: q; r
1
2
sage: r == Integer(mod(14, 12))
True
sage: r == mod(14, 12).lift()
True
sage: r; mod(14, 12)
2
2
\end{lstlisting}
%
In the last code listing, we first converted \verb!mod(14, 12)! to an
integer using \verb!Integer!. The result is then compared with the
remainder \verb!r!. We could also use \verb!mod(14, 12).lift()! to
convert the output of \verb!mod(14, 12)! to an integer prior to
comparing with \verb!r!.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Kid RSA}
\index{cryptography}
\index{Kid RSA}

This section presents Kid RSA~\cite[p.17]{Koblitz1998}, a simplified
version of the RSA\index{RSA} cryptosystem. Neal
Koblitz\index{Koblitz, Neal} developed Kid RSA\index{Kid RSA} as a
tool for teaching cryptography without requiring advanced
mathematics. Most of the necessary concepts and techniques for
understanding Kid RSA are already presented in this chapter. It is
very important to point out that this section is \emph{not} an
introduction to cryptography. Materials presented in this section are
intended for teaching and learning purposes only. If you require more
details about cryptography, please consult specialized texts such
as~\cite{MenezesEtAl1996,Stinson2006,TrappeWashington2006}.

In the Kid RSA system, there are two keys: the
\emph{public key}\index{public key} and its corresponding
\emph{private key}\index{private key}. A public key is used for
\emph{scrambling} messages that you want to keep secret from prying
eyes. The private key corresponding to your public key is used for
\emph{unscrambling} the gibberish resulting from the scrambling
process. In principle, only your private key can unscramble the
gibberish that has been scrambled using your public key. You can let
anyone know your public key. But you should keep your private key only
to yourself. (You don't want anyone to read that scrambled love
letter, right?)

Here is how Kid RSA works. First, Alice chooses four random positive
integers $a, b, A, B$ and computes the following numbers:
%
\begin{align*}
M &= ab - 1 \\[4pt]
e &= AM + a \\[4pt]
d &= BM + b \\[4pt]
n &= \frac{ed - 1}{M}.
\end{align*}
%
Her public key is the pair $(n, e)$ and her private key is $d$.

A message in Kid RSA is any positive integer $x < n$. Alice's friend,
Bob, wants to send her a secret message $x$. Using Alice's public key,
Bob scrambles the message $x$ by multiplying $x$ by $e$, then dividing
the product $xe$ by $n$. The remainder $y$ upon dividing $xe$ by $n$
is the scrambled message. Bob can now send $y$~(the scrambled message)
to Alice via email, the postal service, etc.

To unscramble $y$, Alice multiplies $y$ by her private key $d$ to
obtain the product $yd$. She then divides $yd$ by $n$ and keeps only
the remainder resulting from this division. The remainder upon
dividing $yd$ by $n$ is Bob's original unscrambled message $x$.

As an example, suppose Alice chooses the positive integers
\[
a = 4,\quad
b = 5,\quad
A = 6,\quad
B = 7.
\]
%
\begin{lstlisting}
sage: a = 4; b = 5; A = 6; B = 7
sage: M = a*b - 1
sage: e = A*M + a
sage: d = B*M + b
sage: n = (e*d - 1) / M
sage: n, e
(857, 118)
sage: d
138
\end{lstlisting}
%
Then her public key is $(857, 118)$ and her private key is $138$. Bob
wants to send Alice the message $x = 500$. What is the scrambled
version of $x$?
%
\begin{lstlisting}
sage: x = 500
sage: y = Integer(mod(x*e, n)); y
724
\end{lstlisting}
%
The scrambled version of $x$ is $y = 724$. Bob can now send $y = 724$
to Alice. To unscramble $y = 724$, Alice performs the following
computation:
%
\begin{lstlisting}
sage: mod(y*d, n)
500
sage: x
500
sage: Integer(mod(y*d, n)) == x
True
\end{lstlisting}
%
Thus Bob's original message is successfully unscrambled.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Problems}
\addcontentsline{toc}{section}{Problems}

\begin{enumerate}
\item For the function $f(x) = x^2 + x + 41$, restrict $x$ to take
  only nonnegative integer values.
  \begin{enumerate}
  \item Which integer values of $x$ would result in $f(x)$ being a
    prime number?

  \item What is the largest integer $x$ such that $f(x)$ is prime?

  \item What is the smallest nonnegative integer $x$ such that $f(x)$
    is not prime?
  \end{enumerate}
\end{enumerate}
